package h0817;

import java.util.*;
/**
  * @description 颜色交替的最短路径
  * @author 不知名帅哥
  * @date 2024/8/17 17:42
  * @version 1.0
*/
public class ShortestAlternatingPaths {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        // 创建一个图的结构，graph[i][0] 存储从节点 i 出发的红色边的目标节点
        // graph[i][1] 存储从节点 i 出发的蓝色边的目标节点
        List<Integer>[][] graph = new ArrayList[n][2];
        for (int i = 0; i < n; i++) {
            graph[i][0] = new ArrayList<>();
            graph[i][1] = new ArrayList<>();
        }
        
        // 填充红色边的信息到 graph
        for (int[] edge : redEdges) {
            graph[edge[0]][0].add(edge[1]);
        }
        
        // 填充蓝色边的信息到 graph
        for (int[] edge : blueEdges) {
            graph[edge[0]][1].add(edge[1]);
        }
        
        // 用于存储从起点 0 到每个节点的最短路径长度
        // dist[i][0] 表示通过红色边到达节点 i 的最短路径长度
        // dist[i][1] 表示通过蓝色边到达节点 i 的最短路径长度
        int[][] dist = new int[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0; // 从节点 0 出发，初始路径长度为 0
        dist[0][1] = 0; // 从节点 0 出发，初始路径长度为 0
        
        // 使用队列进行 BFS 遍历
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // 从节点 0，通过红色边出发
        queue.offer(new int[]{0, 1}); // 从节点 0，通过蓝色边出发
        
        // 开始 BFS 遍历
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int curNode = node[0], color = node[1];
            
            // 尝试通过另一种颜色的边进行移动
            for (int nextNode : graph[curNode][1 - color]) {
                // 只有在未被访问过的情况下才更新路径长度
                if (dist[nextNode][1 - color] == Integer.MAX_VALUE) {
                    dist[nextNode][1 - color] = dist[curNode][color] + 1;
                    queue.offer(new int[]{nextNode, 1 - color});
                }
            }
        }
        
        // 计算最终结果
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = Math.min(dist[i][0], dist[i][1]);
            if (answer[i] == Integer.MAX_VALUE) {
                answer[i] = -1; // 如果不可达，则设为 -1
            }
        }
        
        return answer;
    }

    public static void main(String[] args) {
        ShortestAlternatingPaths solver = new ShortestAlternatingPaths();
        int n = 3;
        int[][] redEdges = {{0, 1}, {1, 2}};
        int[][] blueEdges = {{2, 1}};
        System.out.println(Arrays.toString(solver.shortestAlternatingPaths(n, redEdges, blueEdges))); // 输出: [0, 1, 2]
    }


}
